//Given a string s containing only digits, return all possible valid IP addresse
//s that can be obtained from s. You can return them in any order. 
//
// A valid IP address consists of exactly four integers, each integer is between
// 0 and 255, separated by single dots and cannot have leading zeros. For example,
// "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.
//168.1.312" and "192.168@1.1" are invalid IP addresses. 
//
// 
// Example 1: 
// Input: s = "25525511135"
//Output: ["255.255.11.135","255.255.111.35"]
// Example 2: 
// Input: s = "0000"
//Output: ["0.0.0.0"]
// Example 3: 
// Input: s = "1111"
//Output: ["1.1.1.1"]
// Example 4: 
// Input: s = "010010"
//Output: ["0.10.0.10","0.100.1.0"]
// Example 5: 
// Input: s = "101023"
//Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
// 
// Constraints: 
//
// 
// 0 <= s.length <= 3000 
// s consists of digits only. 
// 
// Related Topics 字符串 回溯算法 
// 👍 585 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Restore IP Addresses
class P93RestoreIpAddresses {
    public static void main(String[] args) {
        Solution solution = new P93RestoreIpAddresses().new Solution();
        // TO TEST
        System.out.println(solution.restoreIpAddresses("101023"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<String> res = new ArrayList<>();

        public List<String> restoreIpAddresses(String s) {
            restoreIpAddressesVal(s, new StringBuilder(), new ArrayList<>(), 0, 0);
            return res;
        }

        private void restoreIpAddressesVal(String s, StringBuilder stringBuilder, List<String> list, int i, int count) {
            if (i == s.length() && count == 4) {
                StringBuilder sb = new StringBuilder();
                for (String str : list) {
                    sb.append(str).append(".");
                }
                res.add(sb.substring(0, sb.length() - 1));
            } else if (i >= s.length() || count > 4) {
                return;
            } else if (s.charAt(i) == '0' && stringBuilder.length() == 0) {
                stringBuilder.append(s.charAt(i));
                list.add(stringBuilder.toString());
                restoreIpAddressesVal(s, new StringBuilder(), list, i + 1, count + 1);
                list.remove(list.size() - 1);
            } else {
                for (int j = 0; j < 3; j++) {
                    int num = 0;
                    if (i + j < s.length()) {
                        stringBuilder.append(s.charAt(i + j));
                        String string = stringBuilder.toString();
                        if (!string.equals("")) {
                            num = Integer.parseInt(string);
                        }
                        if (0 <= num && num <= 255) {
                            list.add(stringBuilder.toString());
                            restoreIpAddressesVal(s, new StringBuilder(), list, i + j + 1, count + 1);
                            list.remove(list.size() - 1);
                        }

                    }

                }
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}